package leetcode_ago.bin_tree;

/**
 * 给定一个二叉树，找到两个指定节点的最近公共祖先
 * 最近公共祖先可能有三种情况：1.根左2.根右3.左右
 */
public class Num236_NearestCommonAncestor {
    //找公共祖先时顺便找一下最近公共祖先
    private TreeNode nca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //找到pq的所有祖先
        findCommonAncestor(root,p,q);
        return nca;
    }

    private boolean findCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return false;
        }
        //用整型变量记录是否找到p或q,找到返回1没找到返回0
        int left=findCommonAncestor(root.left,p,q)?1:0;
        int right=findCommonAncestor(root.right,p,q)?1:0;
        int mid=(root==p||root==q)?1:0;
        if(left+right+mid==2){
            //根相加和为2，根节点就是最近公共祖先
            nca=root;
        }
        return left+right+mid>0;
    }
}
